package 程序员面试金典;

import org.junit.Test;

public class 恢复空格 {

    public int respace(String[] dictionary, String sentence) {
        int length = sentence.length();
        //存放装入的字符个数
        int[] dp = new int[length + 1];
        for (int i = 1; i < length; i++) {
            for (String s : dictionary) {
                int len = s.length();
                if (i>=s.length() && sentence.substring(i-len,i).equals(s))
                    dp[i]=Math.max(dp[i],dp[i-len]+len);
                else
                    dp[i]=Math.max(dp[i-1],dp[i]);
            }
        }
        return length-dp[length];
    }
    @Test
    public void test(){
        String s="abc";
        s.replace("a","b");
        System.out.println(s);
    }
}
